/****************************************************************************
 * cmodel_nlpm_trie.h:
 *   nlpm trie definition
 *
 * (C) Copyright Centec Networks Inc.  All rights reserved.
 *
 * Modify History:
 * Revision     : R0.01
 * Author       : cuixl
 * Date         : 2017-Feb-10 10:44
 * Reason       : First Create.
 ****************************************************************************/
#ifndef __NALPM_TRIE_H__
#define __NALPM_TRIE_H__

#include "sal_types.h"

/*#define NALPM_DEBUG_OUT printf*/ /* */
/*#define NALPM_DEBUG_ERR NALPM_DEBUG_OUT*/ /* */
#define NALPM_E_SUCCESS(rv) ((rv) >= 0)/* */
#define NALPM_E_FAILURE(rv) ((rv) < 0)/* */


typedef struct trie_node_s trie_node_t;

typedef enum _node_type_e {
    INTERNAL,
    PAYLOAD,
    MAX
} node_type_e_t;

typedef struct child_node_s {
    trie_node_t *child_node;
} child_node_t;

struct trie_node_s {
#define _MAX_CHILD_     (2)
    child_node_t child[_MAX_CHILD_];
    uint32 skip_addr;/* prefix value: eg 192.168.0.0/16->skip_addr = 0.0.192.168*/
    uint32 count; /* number of payload node counts */

	uint32 skip_len:5;/* eg 192.168.0.0/16-->skip_len = 16*/
    uint32 type:3;
    uint32 bpm:4; /* best prefix match bit map - 32 bits */
    uint32 dirty_flag:4; /* set to 1 when this node is not using */
    uint32 total_skip_len:8; /* total skip len from root to current node */
    uint32 rsv:8;
};

typedef struct trie_s {
    trie_node_t *trie;         /* trie root pointer */
    uint32 v6_key;       /* support 144 bits key, otherwise expect 48 bits key */
} trie_t;

typedef int32 (*trie_callback_f)(trie_node_t *trie, void *datum);

typedef struct trie_bpm_cb_info_s {
    uint32 *pfx; /* prefix buffer pointer from caller space */
    uint32  len;  /* prefix length */
    void         *user_data;
} trie_bpm_cb_info_t;

typedef int32 (*trie_propagate_cb_f)(trie_node_t *trie,
        trie_bpm_cb_info_t *info);

struct sys_nalpm_clone_para_s {
    trie_node_t* father;
    uint8 bit;
};
typedef struct sys_nalpm_clone_para_s sys_nalpm_clone_para_t;

/**
 brief:for dump
*/
struct trie_dump_node_s {
    trie_node_t *root; /* */
    trie_node_t *father; /* */
    uint32 father_lvl; /* */
    void *user_data;
    uint8 lchip;
};
typedef struct trie_dump_node_s trie_dump_node_t;


#define TRIE_ELEMENT(t, p, ep, f) \
    ((t) (((char *) (p)) - (((char *) &((ep)->f)) - ((char *) (ep)))))


#define TRIE_ELEMENT_GET(t, p, f) \
    ((t) (((char *) (p)) - (((char *) &(((t)(0))->f)))))


#define _CLONE_TRIE_NODE_(dest,src) \
    sal_memcpy((dest),(src),sizeof(trie_node_t))

#define _CLONE_ROUTE_TRIE_PAYLOAD_(dest, src) \
    sal_memcpy((dest),(src),sizeof(sys_nalpm_trie_payload_t))


typedef enum _trie_split2_states_e_s {
    TRIE_SPLIT2_STATE_NONE,
    TRIE_SPLIT2_STATE_PRUNE_NODES,
    TRIE_SPLIT2_STATE_DONE,
    TRIE_SPLIT2_STATE_MAX
} trie_split2_states_e_t;


typedef enum _trie_traverse_states_e_s {
    TRIE_TRAVERSE_STATE_NONE,
    TRIE_TRAVERSE_STATE_DELETED,
    TRIE_TRAVERSE_STATE_DONE,
    TRIE_TRAVERSE_STATE_MAX
} trie_traverse_states_e_t;

typedef int32 (*trie_callback_ext_f)(trie_node_t *ptrie, trie_node_t *trie,
                                   trie_traverse_states_e_t *state, void *info);

typedef int32 (*trie_callback_ext1_f)(trie_node_t *ptrie, trie_node_t * trie, trie_traverse_states_e_t *state,
                                uint32 pfx[4], uint8 pfx_len, void *info);


struct trie_chk_info_s {
    uint32* ip;
    uint8 lchip;
    uint8 debug_en;
    uint8 ip_ver;
    uint8 detail;
    uint8 mask_len;
    uint16 vrf_id;
    uint32 ad_idx;
    trie_dump_node_t* dump_node;
    trie_callback_f cb;
};
typedef struct trie_chk_info_s trie_chk_info_t;

typedef int32 (*trie_check_cb_f)(uint8 lchip,trie_chk_info_t* info, uint32* ip);

/*
 * Function:
 *     sys_tsingma_trie_init
 * Purpose:
 *     allocates a trie & initializes it
 */
extern int32 sys_nalpm_trie_init(uint32 max_key_len, trie_t **ptrie);

/*
 * Function:
 *     sys_nalpm_trie_destroy
 * Purpose:
 *     destroys a trie
 */
extern int32 sys_nalpm_trie_destroy(trie_t *trie);

/*
 * Function:
 *     sys_nalpm_trie_insert
 * Purpose:
 *     Inserts provided prefix/length in to the trie
 */
extern int32 sys_nalpm_trie_insert(trie_t *trie,
        uint32 *key,
        /* bpm bit map if bpm management is required,
           passing null skips bpm management */
        uint32 *bpm,
        uint32 length,
        trie_node_t *payload,
        uint8 is_route);

/*
 * Function:
 *     sys_nalpm_trie_delete
 * Purpose:
 *     Deletes provided prefix/length in to the trie
 */
extern int32 sys_nalpm_trie_delete(trie_t *trie,
        uint32 *key,
        uint32 length,
        trie_node_t **payload,
        uint8 is_route);



int32 trie_merge(trie_t *parent_trie,
               trie_node_t *child_trie,
               uint32 *child_pivot,
               uint32 length);


/*
 * Function:
 *     trie_delete
 * Purpose:
 *     Deletes provided prefix/length in to the trie
 */
    int32
trie_delete (trie_t * trie,
        uint32 *key, uint32 length, trie_node_t ** payload);


    int32
trie_destroy (trie_t * trie);


/*
 * Function:
 *     sys_nalpm_trie_dump
 * Purpose:
 *     Dumps the trie pre-order [root|left|child]
 */
extern int32 sys_nalpm_trie_dump(trie_t *trie, trie_callback_f cb, void *user_data);

/*
 * Function:
 *     sys_nalpm_trie_find_lpm
 * Purpose:
 *     Find the longest prefix matched with iven prefix
 */
extern int32 sys_nalpm_trie_find_lpm(trie_t *trie,
        uint32 *key,
        uint32 length,
        trie_node_t **payload,
        uint8 is_route);

/*
 * Function:
 *     sys_nalpm_trie_split
 * Purpose:
 *     Split the trie into 2 based on optimum pivot
 */
extern int32 sys_nalpm_trie_split(trie_t *trie,
        const uint32 max_split_len,
        const int32 split_to_pair,
        uint32 *pivot,
        uint32 *length,
        trie_node_t **split_trie_root,
        uint32 *bpm,
        uint8 payload_node_split,
        const int32 max_split_count);

typedef enum _trie_traverse_order_e_s {
    _TRIE_PREORDER_TRAVERSE,  /* root, left, right */
    _TRIE_INORDER_TRAVERSE,   /* left, root, right */
    _TRIE_POSTORDER_TRAVERSE, /* left, right, root */
    _TRIE_DUMP_TRAVERSE,  /* root, left, right */
    _TRIE_CLONE_TRAVERSE,
    _TRIE_CLEAR_TRAVERSE,
    _TRIE_ARRANGE_FRAGMENT_TRAVERSE,
    _TRIE_PREORDER_AD_ROUTE_TRAVERSE,
    _TRIE_TRAVERSE_MAX
} trie_traverse_order_e_t;

/*
 * Function:
 *     sys_tsingma_trie_traverse
 * Purpose:
 *     Traverse the trie & call the application callback with user data
 */
extern int32 sys_nalpm_trie_traverse(trie_node_t *trie,
        trie_callback_f cb,
        void *user_data,
        trie_traverse_order_e_t order);

extern int32 sys_nalpm_trie_clone(trie_t* trie, trie_t** clone_trie);

extern int32 sys_nalpm_trie_clear(trie_node_t* node);

int32 sys_nalpm_trie_traverse2(trie_t *trie, trie_callback_ext_f cb,
                   void *user_data, trie_traverse_order_e_t order);


int32 sys_nalpm_trie_traverse_lr(trie_node_t *trie,
                                    trie_traverse_states_e_t *state,
                                    trie_callback_ext_f cb,
                                    void *user_data);

int32
sys_nalpm_trie_propagate_prefix(trie_node_t   *trie,
                       uint32             *pfx,
                       uint32              len,
                       trie_callback_f     cb,
                       void               *user_data,
                       uint8 flag);

int32
sys_nalpm_v6_trie_propagate_prefix(trie_node_t   *trie,
                       uint32             *pfx,
                       uint32              len,
                       trie_callback_f     cb,
                       void               *user_data,
                       uint8 flag);


/*=================================
 * Used by internal functions only
 *================================*/


typedef enum _trie_split_states_e_s {
    TRIE_SPLIT_STATE_NONE,
    TRIE_SPLIT_STATE_PAYLOAD_SPLIT,
    TRIE_SPLIT_STATE_PAYLOAD_SPLIT_DONE,
    TRIE_SPLIT_STATE_PRUNE_NODES,
    TRIE_SPLIT_STATE_DONE,
    TRIE_SPLIT_STATE_MAX
} trie_split_states_e_t;

#define SYS_NALPM_CONVERT_TO_MSB(ipaddr, masklen, hw_ipaddr, ip_ver) \
    if (0 == masklen) \
    {\
        *hw_ipaddr = 0;\
    }\
    else\
    {\
        if ( CTC_IP_VER_4 == ip_ver )\
        {\
            *hw_ipaddr = (*ipaddr << (32 - masklen));\
        }\
        else\
        {\
            if (masklen <= 32)\
            {\
                *(hw_ipaddr + 0) = *(ipaddr + 3) << (32 - masklen);\
            }\
            else if(32 < masklen &&  masklen < 64)\
            {\
                *(hw_ipaddr + 0) = (*(ipaddr + 2) << (64 - masklen)) + (*(ipaddr + 3) >> (32 - (64 - masklen)));\
                *(hw_ipaddr + 1) = (*(ipaddr + 3) << (64 - masklen));\
            }\
            else if(masklen == 64)\
            {\
                *(hw_ipaddr + 0) = *(ipaddr + 2);\
                *(hw_ipaddr + 1) = *(ipaddr + 3);\
            }\
            else if(64 < masklen &&  masklen < 96)\
            {\
                *(hw_ipaddr + 0) = (*(ipaddr + 1) << (96 - masklen)) +  (*(ipaddr + 2) >> (32 - (96 - masklen)));\
                *(hw_ipaddr + 1) = (*(ipaddr + 2) << (96 - masklen)) +  (*(ipaddr + 3) >> (32 - (96 - masklen)));\
                *(hw_ipaddr + 2) = (*(ipaddr + 3) << (96 - masklen));\
            }\
            else if(masklen == 96)\
            {\
                *(hw_ipaddr + 0) = *(ipaddr + 1);\
                *(hw_ipaddr + 1) = *(ipaddr + 2);\
                *(hw_ipaddr + 2) = *(ipaddr + 3);\
            }\
            else if(96 < masklen &&  masklen < 128)\
            {\
                *(hw_ipaddr + 0) = (*(ipaddr + 0) << (128 - masklen)) + (*(ipaddr + 1) >> (32 - (128 - masklen)));\
                *(hw_ipaddr + 1) = (*(ipaddr + 1) << (128 - masklen)) + (*(ipaddr + 2) >> (32 - (128 - masklen)));\
                *(hw_ipaddr + 2) = (*(ipaddr + 2) << (128 - masklen)) + (*(ipaddr + 3) >> (32 - (128 - masklen)));\
                *(hw_ipaddr + 3) = (*(ipaddr + 3) << (128 - masklen));\
            }\
            else if(masklen == 128)\
            {\
                *(hw_ipaddr + 0) = *(ipaddr + 0);\
                *(hw_ipaddr + 1) = *(ipaddr + 1);\
                *(hw_ipaddr + 2) = *(ipaddr + 2);\
                *(hw_ipaddr + 3) = *(ipaddr + 3);\
            }\
        }\
    }\




#define SYS_NALPM_CONVERT_TO_LSB(key, length, ip_ver) \
    if (ip_ver)\
    {\
        if (length <= 32)\
        {\
            key[3] = (key[0] >> (32 - length));\
            key[0] = 0;\
        }\
        else if(length < 64)\
        {\
            key[3] = (key[1] >> (64 - length)) + (key[0] << (length - 32));\
            key[2] = (key[0] >> (64 - length));\
            key[0] = 0;\
            key[1] = 0;\
        }\
        else if(length == 64)\
        {\
            key[3] = key[1];\
            key[2] = key[0];\
            key[1] = 0;\
            key[0] = 0;\
        }\
        else if(length  < 96)\
        {\
            key[3] = (key[2] >> (96 - length)) + (key[1] << (length - 64));\
            key[2] = (key[1] >> (96 - length)) + (key[0] << (length - 64));\
            key[1] = (key[0] >> (96 - length));\
            key[0] = 0;\
        }\
        else if(length == 96)\
        {\
            key[3] = key[2];\
            key[2] = key[1];\
            key[1] = key[0];\
            key[0] = 0;\
        }\
        else if(length  < 128)\
        {\
            key[3] = (key[3] >> (128 - length)) + (key[2] << (length - 96));\
            key[2] = (key[2] >> (128 - length)) + (key[1] << (length - 96));\
            key[1] = (key[1] >> (128 - length)) + (key[0] << (length - 96));\
            key[0] = (key[0] >> (128 - length));\
        }\
        else if(length == 128)\
        {\
            key[3] = key[3];\
            key[2] = key[2];\
            key[1] = key[1];\
            key[0] = key[0];\
        }\
    }\
    else\
    {\
        key[0] = key[0] >> (32 - length);\
    }\



#define SYS_NALPM_IP_MAP(ipaddr, masklen, hw_ipaddr, ip_ver) \
    if (0 == masklen) \
    {\
        *hw_ipaddr = 0;\
    }\
    else\
    {\
        if ( CTC_IP_VER_4 == ip_ver )\
        {\
            *hw_ipaddr = (*ipaddr << (32 - masklen));\
        }\
        else\
        {\
            if (masklen <= 32)\
            {\
                *(hw_ipaddr + 3) = *(ipaddr + 3) << (32 - masklen);\
            }\
            else if(32 < masklen &&  masklen < 64)\
            {\
                *(hw_ipaddr + 3) = (*(ipaddr + 2) << (64 - masklen)) + (*(ipaddr + 3) >> (32 - (64 - masklen)));\
                *(hw_ipaddr + 2) = (*(ipaddr + 3) << (64 - masklen));\
            }\
            else if(masklen == 64)\
            {\
                *(hw_ipaddr + 3) = *(ipaddr + 2);\
                *(hw_ipaddr + 2) = *(ipaddr + 3);\
            }\
            else if(64 < masklen &&  masklen < 96)\
            {\
                *(hw_ipaddr + 3) = (*(ipaddr + 1) << (96 - masklen)) +  (*(ipaddr + 2) >> (32 - (96 - masklen)));\
                *(hw_ipaddr + 2) = (*(ipaddr + 2) << (96 - masklen)) +  (*(ipaddr + 3) >> (32 - (96 - masklen)));\
                *(hw_ipaddr + 1) = (*(ipaddr + 3) << (96 - masklen));\
            }\
            else if(masklen == 96)\
            {\
                *(hw_ipaddr + 3) = *(ipaddr + 1);\
                *(hw_ipaddr + 2) = *(ipaddr + 2);\
                *(hw_ipaddr + 1) = *(ipaddr + 3);\
            }\
            else if(96 < masklen &&  masklen < 128)\
            {\
                *(hw_ipaddr + 3) = (*(ipaddr + 0) << (128 - masklen)) + (*(ipaddr + 1) >> (32 - (128 - masklen)));\
                *(hw_ipaddr + 2) = (*(ipaddr + 1) << (128 - masklen)) + (*(ipaddr + 2) >> (32 - (128 - masklen)));\
                *(hw_ipaddr + 1) = (*(ipaddr + 2) << (128 - masklen)) + (*(ipaddr + 3) >> (32 - (128 - masklen)));\
                *(hw_ipaddr + 0) = (*(ipaddr + 3) << (128 - masklen));\
            }\
            else if(masklen == 128)\
            {\
                *(hw_ipaddr + 3) = *(ipaddr + 0);\
                *(hw_ipaddr + 2) = *(ipaddr + 1);\
                *(hw_ipaddr + 1) = *(ipaddr + 2);\
                *(hw_ipaddr + 0) = *(ipaddr + 3);\
            }\
        }\
    }

#define SYS_NALPM_IP_MAP_REVERT(ipaddr, masklen, hw_ipaddr, ip_ver) \
    if (0 == masklen) \
    {\
        *hw_ipaddr = 0;\
    }\
    else\
    {\
        if ( CTC_IP_VER_4 == ip_ver )\
        {\
            *hw_ipaddr = (*ipaddr >> (32 - masklen));\
        }\
        else\
        {\
            if (masklen <= 32)\
            {\
                *(hw_ipaddr + 3) = *(ipaddr + 3) >> (32 - masklen);\
            }\
            else if(32 < masklen &&  masklen < 64)\
            {\
                *(hw_ipaddr + 3) = (*(ipaddr + 2) >> (64 - masklen)) + (*(ipaddr + 3) << (32 - (64 - masklen)));\
                *(hw_ipaddr + 2) = (*(ipaddr + 3) >> (64 - masklen));\
            }\
            else if(masklen == 64)\
            {\
                *(hw_ipaddr + 3) = *(ipaddr + 2);\
                *(hw_ipaddr + 2) = *(ipaddr + 3);\
            }\
            else if(64 < masklen &&  masklen < 96)\
            {\
                *(hw_ipaddr + 3) = (*(ipaddr + 1) >> (96 - masklen)) +  (*(ipaddr + 2) << (32 - (96 - masklen)));\
                *(hw_ipaddr + 2) = (*(ipaddr + 2) >> (96 - masklen)) +  (*(ipaddr + 3) << (32 - (96 - masklen)));\
                *(hw_ipaddr + 1) = (*(ipaddr + 3) >> (96 - masklen));\
            }\
            else if(masklen == 96)\
            {\
                *(hw_ipaddr + 3) = *(ipaddr + 1);\
                *(hw_ipaddr + 2) = *(ipaddr + 2);\
                *(hw_ipaddr + 1) = *(ipaddr + 3);\
            }\
            else if(96 < masklen &&  masklen < 128)\
            {\
                *(hw_ipaddr + 3) = (*(ipaddr + 0) >> (128 - masklen)) + (*(ipaddr + 1) << (32 - (128 - masklen)));\
                *(hw_ipaddr + 2) = (*(ipaddr + 1) >> (128 - masklen)) + (*(ipaddr + 2) << (32 - (128 - masklen)));\
                *(hw_ipaddr + 1) = (*(ipaddr + 2) >> (128 - masklen)) + (*(ipaddr + 3) << (32 - (128 - masklen)));\
                *(hw_ipaddr + 0) = (*(ipaddr + 3) >> (128 - masklen));\
            }\
            else if(masklen == 128)\
            {\
                *(hw_ipaddr + 3) = *(ipaddr + 0);\
                *(hw_ipaddr + 2) = *(ipaddr + 1);\
                *(hw_ipaddr + 1) = *(ipaddr + 2);\
                *(hw_ipaddr + 0) = *(ipaddr + 3);\
            }\
        }\
    }

extern int32 sys_nalpm_trie_fuse_child(trie_node_t *trie, int32 bit);

extern int32 sys_nalpm_print_trie_node(trie_node_t *trie, void *datum);

int32
sys_trie_find_lpm_prefix(trie_t * trie,
                   uint32 *pivot,
                   uint32 *length);


int32
sys_trie_check_node (trie_t * trie,
                    uint32 *key,
                    uint32  key_len,
                    trie_check_cb_f cb,
                    trie_chk_info_t *info);


#endif /* __NALPM_TRIE_H__ */

